#include <stdio.h>
#include <stdlib.h>

int coin_greedy(int money, int coins[], int n)
{
    int i, count;

    for (i = 0, count = 0; i < n; i++) {
        while (money >= coins[i]) {
            count ++;
            money -= coins[i];
        }
    }

    return count;
}

int coin_dynamic(int money, int coins[], int n)
{
    int i, j, min, *count, ret;
    
    count = malloc(sizeof(int) * (money+1));

    count[0] = 0;
    for (i = 1; i <= money; i++) {
        min = money+1;
        for (j = 0; j < n; j++) {
            if (i >= coins[j]) {
                if (min > count[i-coins[j]])
                    min = count[i-coins[j]];
            }
        }
        if (min == money+1)
            count[i] = 0;
        else
            count[i] = min + 1;  
    }

    ret = count[money];
    free(count);

    return ret;
}

int main(int argc, char *argv[])
{
    int money = 23789;
    int coins[] = {100, 50, 20, 10, 5, 2, 1};
    
    printf("%d\n", coin_greedy(money, coins, 7));
    printf("%d\n", coin_dynamic(money, coins, 7));

    return 0;
}
